package lc.q250_300;

import java.util.Arrays;

public class Q274 {

    public static void main(String[] args) {
        Q274 q274 = new Q274();
        System.out.println(q274.hIndex2(new int[]{1,3,1}));
    }

    public int hIndex2(int[] citations) {
        // 使用计数排序
        int n = citations.length;
        int[] res = new int[n + 1];
        for (int citation : citations) {
            if (citation > n) {
                res[n]++;
            } else {
                res[citation]++;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            if (res[i + 1] >= i + 1) {
                return i + 1;
            }
            res[i] = res[i] + res[i + 1];
        }
        return 0;
    }

    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        // 如果所有都是0
        int n = citations.length;
        if (citations[n - 1] == 0) {
            return 0;
        }
        int result = citations.length;
        while (result >= 1 && citations[n - result] < result) {
            result --;
        }
        return result;
    }
}
